package Tree;


import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;

public class TreeNode {

    private TreeNode left;
    private int val;
    private TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(TreeNode left, int val, TreeNode right) {
        this.left = left;
        this.val = val;
        this.right = right;
    }

    //根据后缀表达式建树
    //21-3*
    public static TreeNode SuffixExpressions(String s) {
        Stack<TreeNode> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            switch (ch) {
                case '-','+','*','/' -> {
                    TreeNode right = stack.pop();
                    TreeNode left = stack.pop();
                    TreeNode temp = new TreeNode(ch);
                    temp.left = left;
                    temp.right = right;
                    stack.push(temp);

                }
                default -> {
                    stack.push(new TreeNode(ch));
                }
            }
        }
        return stack.pop();
    }

    //非递归中序遍历
    public void mid(TreeNode root) {
        TreeNode node = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        while ( node != null || !stack.isEmpty()) {

            if (node != null) {

                stack.push(node);
                node = node.left;
            }else {
                TreeNode pop = stack.pop();
                System.out.print((char)(pop.val) + " ");
                node = pop.right;
            }
        }

    }


    //非递归前序遍历
    public void prev(TreeNode root) {
        TreeNode node = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        while ( node != null || !stack.isEmpty()) {

            if (node != null) {
                System.out.print((char)(node.val) + " ");
                stack.push(node);
                node = node.left;
            }else {
                TreeNode pop = stack.pop();
                node = pop.right;
            }
        }

    }

    //非递归后序遍历
    public void post(TreeNode root) {
        TreeNode node = root;
        LinkedList<TreeNode> stack = new LinkedList<>();
        TreeNode pop = null;
        while ( node != null || !stack.isEmpty()) {

            if (node != null ) {
                stack.push(node);
                node = node.left;
            }else {
                TreeNode peek = stack.peek();
                if (peek.right == null || peek.right == pop) {
                    pop = stack.pop();
                    System.out.print((char) pop.val + " ");
                }else {
                    node = peek.right;
                }

            }

        }
    }

    public void recursion(TreeNode node) {
        if (node == null) {
            return;
        }
        System.out.print(node.val + " ");
        recursion(node.left);
        recursion(node.right);
    }

    //根据前序与中序建树
    public static TreeNode prevAndMid(int[] prev, int[] mid) {

        if (prev.length == 0) {
            return  null;
        }
        int rootVal = prev[0];
        TreeNode root = new TreeNode(rootVal);
        for (int i = 0; i < mid.length; i++) {
            if (rootVal == mid[i]) {

                int[] midLeft = Arrays.copyOfRange(mid,0,i);
                int[] midRight = Arrays.copyOfRange(mid,i + 1,mid.length);

                int[] prevLeft = Arrays.copyOfRange(prev,1,i + 1);
                int[] prevRight = Arrays.copyOfRange(prev,i + 1,mid.length);

                root.left = prevAndMid(prevLeft,midLeft);
                root.right = prevAndMid(prevRight,midRight);
                break;
            }
        }
        return root;
    }

    //根据中后序建树
    public static TreeNode midAndPost(int[] mid, int[] post) {

        if (mid.length == 0) {
            return null;
        }
        int rootVal = post[post.length - 1];
        TreeNode root = new TreeNode(rootVal);
        for (int i = 0; i < mid.length; i++) {
            if (mid[i] == rootVal) {

                int[] midLeft = Arrays.copyOfRange(mid,0,i);
                int[] midRight = Arrays.copyOfRange(mid,i+1,mid.length);

                int[] postLeft = Arrays.copyOfRange(post,0,i);
                int[] postRight = Arrays.copyOfRange(post,i,mid.length - 1);

                root.left = midAndPost(midLeft,postLeft);
                root.right = midAndPost(midRight,postRight);
                break;
            }

        }
        return root;
    }

}


